package com.msb.平衡树;

// 测试链接：https://leetcode.com/problems/balanced-binary-tree
// 12min
public class Code02_BalancedBinaryTree_easy {

	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;

		TreeNode(int val) {
			this.val = val;
		}
	}

	public static class Info {
		int height;
		boolean isBalance;
	}

	// 用递归, 左右树都必须是平衡的, 然后看自己是否平衡, 然后树高信息返回
	public boolean isBalanced(TreeNode root) {
		return balanced(root).isBalance;
	}

	public Info balanced(TreeNode root) {
		// 递归
		Info info = new Info();
		if (root == null) {
			info.isBalance = true;
			info.height = 0;
			return info;
		}
		Info leftI = balanced(root.left);
		Info rightI = balanced(root.right);
		info.height = Math.max(leftI.height, rightI.height) + 1;
		info.isBalance = leftI.isBalance && rightI.isBalance && Math.abs(leftI.height - rightI.height) < 2;
		return info;
	}
}
